/*
 * Given a string S, find the longest palindromic substring in S. 
 * You may assume that the maximum length of S is 1000, and there 
 * exists one unique longest palindromic substring.
 */

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        String maxStr = "";
        int maxLen = 0;
        
        if(s.length() > 0)
        {
            maxStr = ""+s.charAt(0);
            maxLen = 1;
        }
        
        for(int i = 0 ; i < s.length()-1 ; i ++)
        {
            if(s.charAt(i) == s.charAt(i+1))
            {
                if(maxLen < 2) {
                    maxLen = 2;
                    maxStr = s.substring(i,i+2);
                }
                
                int low = i-1, high = i+2;
                while(low >=0 && high<s.length() && s.charAt(low) == s.charAt(high))
                {
                    if(maxLen < high - low + 1) {
                        maxLen = high - low + 1;
                        maxStr = s.substring(low, high+1);
                    }
                    
                    low--;
                    high++;
                }
            }
            int low = i-1, high = i+1;
            while(low >=0 && high<s.length() && s.charAt(low) == s.charAt(high))
            {
                if(maxLen < high - low + 1) {
                    maxLen = high - low + 1;
                    maxStr = s.substring(low, high+1);
                }
                low--;
                high++;
            }
        }
        
        return maxStr;
    }
}